package com.zbcn.algorithm;

import java.util.Arrays;

/**
 * kmp 算法
 *
 * @author likun
 * @since 2022/5/12 8:33
 */
public class T15_KMP {

    public static void main(String[] args) {
        char[] a = {'a','b','a','b','a','e','a','b','a','c','a','b','a','b','a','c','d'};
        char[] b = {'a','b','a','b','a','c','d'};
        int n = a.length;
        int m = b.length;
        int[] next = getNext(b, m);
        int[] next2 = getNext2(b, m);
        System.out.println("next=" + Arrays.toString(next));
        System.out.println("next2=" + Arrays.toString(next2));


        //int kmp = kmp(a, n, b, m);
        int kmp = bruteForce(a, n, b, m);
        System.out.println(kmp);
    }


    /**
     * a b 分别是主串和模式串，n,m 分别是主串和模式串的长度
     * @param a
     * @param n
     * @param b
     * @param m
     * @return
     */
    public static int kmp(char[] a, int n, char[] b, int m){

        int[] next = getNext(b,m);
        int j = 0;
        for(int i = 0; i < n; ++i){
            // 一直找到 a[i] 和 b[j]
            while (j > 0 && a[i] != b[j]){
                // 如果主串和模式串中的字符出现不相等，模式串要回溯的位置
                j = next[j-1] + 1;
            }
            if (a[i] == b[j]){
                // 如果主串和模式串相等，则 比较一下位
                ++j;
            }
            // 找到匹配模式串的了
            if (j == m){
                return i- m +1;
            }
        }
        // 没有找到
        return -1;

    }

    /**
     * 失效函数的求解方法（求解next 数组）：数组的下标是每个前缀的结尾字符下标，数组的值是 这个前缀的最长可匹配的前缀子串的结尾字符下标
     * b 模式 模式串
     * m 模式串的长度
     */
    private static int[] getNext(char[] b, int m){
        int[] next = new int[m];
        // 模式串中size 为 1 子串中（前缀结尾下标 为 0）， 最长可匹配前缀子串不存在，所以 value = -1
        next[0] = -1;
        // 最长可匹配前缀子串的最后一个字符，默认为-1
        int k = -1;
        // 模式串的后缀子串，所以下标从 1 开始
        for (int i = 1; i < m; ++i){
            // 判断前拽子串和后缀子串是否相等
            while (k!=-1 && b[k+1] != b[i]){
                k = next[k];
            }
            if (b[k+1] == b[i]){
                ++k;
            }
            next[i] = k;
        }
        System.out.println(next);
        return next;
    }


    /**
     * 低效的方式求解next 数组
     * next[i]  P[0] ~ P[i] 这一个子串,使得 前k个字符恰等于后k个字符 的最大的k (k不能取i+1（因为这个子串一共才 i+1 个字符，自己肯定与自己相等，就没有意义了）)
     * fixme 该方法有问题，需要重新写，逻辑没想清楚
     * @param b
     * @param m
     * @return
     */
    private static int[] getNext2(char[] b, int m){
        int[] next = new int[m];
        // 模式串的前缀子串中
        for (int i = 0; i < m; ++i){
            //模式串中size 为 1 子串中（前缀结尾下标 为 0）， 最长可匹配前缀子串不存在，所以 value = -1
            if (i == 0){
                next[i] = -1;
                continue;
            }
            // 最长可匹配前缀子串的最后一个字符，默认为-1
            int k = -1;
            //模式串子的最长可匹配的前缀子串的结尾字符下标
            for (int j =m-i; j < i;j++){
                if (b[j] == b[i -j]){
                    k++;
                }
            }
            next[i] = k;
        }
        System.out.println(next);
        return next;
    }


    /**
     * 暴力匹配
     * @param a
     * @param n
     * @param b
     * @param m
     * @return
     */
    public static int bruteForce(char[] a, int n, char[] b, int m){
        // 要匹配的最后一个位置
        int lenS = n-m;
        for (int i = 0; i <= lenS; i++){
            boolean flag = true;
            for (int j = 0; j < m; j++){
                if (a[i + j] != b[j]){
                    flag = false;
                    break;
                }
            }
            if (flag){
                return i;
            }
        }
        return -1;

    }


    //全局变量
    private static final int SIZE = 256;

    /**
     * 生成 三列表
     * @param b ascii 码表
     * @param m 模式串长度
     * @param bc 生成的三列表
     */
    private void generateBC(char[] b, int m, int[] bc){
        for (int i=0; i < SIZE; i++){
            bc[i] = -1; //初始化bc
        }
        for (int i= 0; i < m; ++i){
            int ascii = (int)b[i]; // 计算 b[i] 的 ASCII
            bc[ascii] = i;
        }
    }


    /**
     *  boyer - Moore 实现字符串匹配算法 ---坏字符规则
     * @param a 原始主串
     * @param n 原始主串长度
     * @param b 模式串
     * @param m 模式串长度
     * @return
     */
    public  int bm(char[] a, int n, char[] b, int m){
        // 记录模式串中每个字符最后出现的问题
        int[] bc = new int[SIZE];
        // 构建坏字符HASH 表
        generateBC(b,m,bc);

        // 开始查询逻辑```````````````````

        // 表示模式串与主串对齐的第一个字符
        int i = 0;
        // 循环主串
        while (i < n-m ) {
            // 模式串的最后一个位置
            int j;
            // 模式串从后往前匹配,寻找坏字符串
            for (j = m-1; j>0;--j){
                //寻找到坏字符串
                if (b[j] != a[i + j]){
                    // 跳出循环
                    break;
                }
            }

            if (j < 0){
                //说明没有找到坏字符，匹配成功. 返回模式串 和主串匹配成功的第一个字符的位置 i
                return i;
            }
            // 未匹配成功，j 表示坏字符位置，将 模式串 往后滑动 j - bc[(int)a[i+j]] 位
            i = i+ ( j - bc[(int) a[i+j]]);
        }
        return -1;

    }

    /**
     *
     * @param b 模式串
     * @param m 模式串长度
     * @param suffix  公共后缀子串的起始下标存储数组：数组的下标 k， 表示 后缀子串长度，下标对应的数组值存储的是在模式串中跟好后缀{u} 相匹配的子串{u*} 的起始下标值
     * @param prefix 来记录模式串的后缀子串是否能匹配模式串的前缀子串（公共后缀子串也是模式串的前缀子串）
     */
    private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix){
        // 初始化
        for (int i= 0; i < m; i++){
            suffix[i] = -1;
            prefix[i] = false;
        }

        for (int i = 0; i < m-1;++i){
            //公共后缀子串的起始下标
            int j = i;
            //公共后缀子串的长度
            int k = 0;

            // b[0,m-1] 中求公共后缀子串，从后往前推
            while (j >= 0 && b[j] == b[m-1-k]){
                --j;
                ++k;
                // j+1 表示 公共后嘴子串在 b[0,i] 中的起始下标
                suffix[k] = j+1;
            }
            if (j==-1){
                prefix[k] = true;
            }
        }


    }


    /**
     *  boyer - Moore 实现字符串匹配算法 ---好后缀规则
     * @param a 原始主串
     * @param n 原始主串长度
     * @param b 模式串
     * @param m 模式串长度
     * @return
     */
    public int bm2(char[] a, int n, char[] b, int m){
        // bc 记录模式串中吗，没个字符出现的最后位置
        int[] bc = new int[SIZE];
        // 构建 坏字符hash 表
        generateBC(b,m,bc);
        // 数组的下标 k， 表示 后缀子串长度，下标对应的数组值存储的是在模式串中跟好后缀{u} 相匹配的子串{u*} 的起始下标值
        int[] suffix = new int[m];
        //来记录模式串的后缀子串是否能匹配模式串的前缀子串
        boolean[] prefix = new boolean[m];
        //生成以上数据
        generateGS(b,m,suffix,prefix);

        // 模式串与主串对齐的第一个 位置
        int i = 0;
        //循环主串
        while( i < n-m){
            // 模式串的最后一个位置
            int j;
            // 模式串和主串从后往前匹配
            for (j = n-m; j>0;j--){
                if (a[i+j] !=b[j]){
                    break; // 坏字符对应的模式串的下标 是 j
                }
            }
            if (j < 0){
                return i; // 匹配成功，返回主串与模式串中第一个匹配字符的位置（i 表示在主串中的位置）
            }
            // 模式串中好后缀的前缀子串对应的移动距离
            int x = j -bc[(int)a[i+j]];
            int y = 0;
            // 判断是否有好后嘴
            if (j < m-1){
                y = moveByGS(j,m,suffix,prefix);
            }

            i = i+ Math.max(x,y);
        }
        return  -1;
    }


    /**
     * 好后缀规则，移动距离测算
     * @param j 坏字符对应的模式串中的字符索引，
     * @param m 模式串的长度
     * @param suffix
     * @param prefix
     * @return
     */
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
        // 好后缀的长度
        int k = m-1 -j;
        // 表示好后缀存在公共前缀子串
        if (suffix[k] != -1){
            return  j - suffix[k] +1;
        }
        // 好后缀的后缀子串，是否从在公顷前缀子串 ， r 表示好后缀子串的后缀子串的起始下标
        for (int r = j +2; r < m-1;r++){
            if (prefix[m-r] == true){
                return r;
            }
        }
        return m;
    }


}
